package com.example.recur;

import java.util.Stack;

/**
 * @Date 2023-07-02
 * @Author Jonathan
 */
public class Link {
    Integer cur = 0;

    public static void main(String[] args) {
        Node node1 = new Node(4);
        Node node2 = new Node(5);
        Node node3 = new Node(1);
        Node node4 = new Node(9);
        node1.next = node2;
        node2.next = node3;
        node3.next = node4;
        Link link = new Link();
        link.printLink(node1);
        System.out.print("\n");
        link.deleteNode(node2);
        link.printLink(node1);

//        Node node1 = link.removeElement(node, 1);
//        Node reverse = link.reverseList(node);
//        System.out.print("\nreversed:");
//        link.printLink(reverse);
//        System.out.print("\nremoveNth:");
//        Node removedNth = link.removeNth(reverse, 1, 3);
//        Node removedNth = link.removeNthFromEnd(reverse, 1);
//        link.printLink(removedNth);


    }

    /**
     * 借尸还魂删除节点
     */
    public void deleteNode(Node node) {
        Node cur = node;
        Node next = cur.next;
        while (next.next != null) {
            cur.value = next.value;
            cur = cur.next;
            next = next.next;
        }
        cur.value = next.value;
        cur.next = null;
    }


    /**
     * 删除链表里值为指定值的节点
     */

    public Node removeElement(Node head, int val) {
        // 最小子问题
        if (head == null) return null;
        // 删除子链表中指定值的节点
        Node ret = removeElement(head.next, val);
        // 处理当前节点
        // 也即处理头结点
        if (head.value != val) {
            head.next = ret;
            return head;
        } else {
            return ret;
        }
    }

    public Node removeElement1(Node head, int val) {
        // 最小子问题
        if (head == null) return null;
        // 删除子链表中指定值的节点
        head.next = removeElement1(head.next, val);
        // 处理头结点
        return head.value == val ? head.next : head;
    }

    /**
     * 反转链表
     * 终于自己写出来了
     */
    public Node reverseList(Node node) {
        // 最小子问题
        // 递
        if (node == null || node.next == null) {
            return node;
        }
        // 返回的是新的头结点
        Node ret = reverseList(node.next);
        // reverse这个动作只能由 当前节点node来完成
        // 容易写成  ret.next = node
        // 归  在归的时候 实现这个反转
        node.next.next = node;
        node.next = null;
        return ret;
    }

    /**
     * 删除第n个节点
     *
     * @param node
     * @param cur
     * @param nth
     * @return
     */
    public Node removeNth(Node node, int cur, int nth) {
        if (node == null) {
            return null;
        }
        if (cur == nth) {
            return node.next;
        }
        node.next = removeNth(node.next, ++cur, nth);
        return node;
    }

    public Node removeNthFromEnd(Node node, int nth) {
        if (node == null) {
            return null;
        }

        node.next = removeNthFromEnd(node.next, nth);
        ++cur;
        // 当前节点是倒数第n个
        if (cur == nth) {
            return node.next;
        }
        return node;

    }


    /**
     * 打印链表
     *
     * @param head
     */
    void printLink(Node head) {
        if (head == null) {
            return;
        }

        Stack<Node> stack = new Stack<>();
        stack.push(head);
        while (!stack.isEmpty()) {
            Node node = stack.pop();
            if (node == null) return;
            System.out.print(node.value + " ");
            stack.push(node.next);
        }
    }


    static class Node {
        int value;
        Node next;

        public Node(int value) {
            this.value = value;
        }

        public Node(int value, Node next) {
            this.value = value;
            this.next = next;
        }
    }
}
